package 动态规划.子序列.最长递增子序列;

import java.util.Arrays;
import java.util.Comparator;

public class 俄罗斯套娃信封问题_354 {
    public int maxEnvelopes(int[][] envelopes) {

        int N = envelopes.length;
        if (N == 0) {
            return 0;
        }

        Arrays.sort(envelopes, new Comparator<int[]>() {
            //按照每个信封的宽度进行升序排列，若宽度一样，则按高度降序排列
            public int compare(int[] a, int[] b) {
                /*
                    a[0]、b[0]分别代表前一个、后一个数组的宽度
                    a[1]、b[1]分别代表前一个、后一个数组的宽度
                */
                return a[0] == b[0] ? b[1] - a[1] : a[0] - b[0];
            }
        });
        int[] target = new int[N];

        for (int i = 0; i < N; i++) {
            target[i] = envelopes[i][1];//把排序后的高度单独提取出来
        }

        return lengthOfLIS(target);

    }


    //用来求最长递增子序列。这里稍微修改一下作为辅助方法
    public int lengthOfLIS(int[] nums) {

        if (nums.length == 0) {
            return 0;
        }
        int N = nums.length;
        //dp[i]存放的是：以nums[i]结尾的最长递增子序列的长度
        int[] dp = new int[N];


        //base case：将dp[]都初始化为1
        Arrays.fill(dp, 1);

        for (int i = 0; i < N; i++) {//i=N-1就是dp[]的最后一个元素了，原为dp[]的长度和nums[]的相同
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        int res = 0;
        //来遍历一次经过整理的dp[]，找出最大值
        for (int i = 0; i < dp.length; i++) {
            res = Math.max(res, dp[i]);
        }

        return res;

    }
}
